1. Field of the Invention
This disclosure relates generally to computer-aided simulation of large circuits using a hierarchical data structure, and more specifically, to removing redundant calculations in sparse matrix operations in circuit simulation by utilizing previously computed values corresponding to structurally identical blocks within the circuit when it is determined that the blocks share substantially the same state within a predetermined error range.
2. Description of the Related Art
Computer-aided circuit simulation uses mathematical models to replicate the behavior of an electronic circuit. Simulating circuit behavior can improve design efficiency by making faulty designs known and providing insight into the behavior of the circuit before the circuit is actually fabricated. Typical circuit simulators can include both analog and event-driven digital simulation capabilities. An entire mixed signal analysis can be driven from one integrated schematic.
Circuit simulation of complex circuit systems (e.g., systems on a chip) may involve a substantial number of transistors and other devices. In general, there are two types of computer-aided circuit simulation systems, including “flat solvers” and “hierarchical solvers.” A flat solver performs simulation at the device level (such as down to the individual transistors, resistors, capacitors, etc.). A netlist describing a large complex circuit system, however, can be very hierarchical in nature with many repeated sub-blocks, such as memory arrays, input/output (I/O) banks, digital logic (e.g., OR gates, AND gates, inverters, etc.), and the like. Hierarchical solvers were developed to exploit latency independently for each cell or block in the hierarchy. However, since flat solvers have significantly evolved, conventional hierarchical solutions exploiting only circuit latency has heretofore not provided a significant advantage in the context of high accuracy circuit simulation. For example, matrix ordering naturally arranges the matrix into block bordered diagonal form and allows flat solvers to exploit data locality. Flat solvers are also able to exploit latency. Hierarchical solvers are not always more efficient. Arranging the matrix computations hierarchically may, in fact, increase the overall operation count which may cause an undesired increase in simulation time.
Conventional hierarchical approaches have not provided significant acceleration of circuit simulation as compared to flat solver approaches. Furthermore, certain hierarchical approaches ignore differences in node voltages between similar block types resulting in undesired loss of accuracy. It is therefore desirable to speed up hierarchical or block level simulation of integrated circuit systems without suffering any loss in accuracy.